package guide;

import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 18-4-13 上午10:09
 */
public class Array {
    public void spiralOrderPrint(int [][] matrix) {
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            printEdge(matrix, tR++, tC++, dR--, dC--);
        }
    }
    private void printEdge(int [][] matrix, int tR, int tC, int dR, int dC) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                System.out.println(matrix[tR][i] + " ");
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                System.out.println(matrix[i][tC] + " ");
            }
        } else {
            int curC = tC;
            int curR = tR;
            while (curC != dC) {
                System.out.println(matrix[curR][curC] + " ");
                curC++;
            }
            while (curR != dR) {
                System.out.println(matrix[curR][curC] + " ");
                curR++;
            }
            while (curC != tC) {
                System.out.println(matrix[curR][curC] + " ");
                curC--;
            } while (curR != tC) {
                System.out.println(matrix[curR][curC] + " ");
                curR--;
            }

        }
    }

    public void rotate(int[][] martix) {
        int tR = 0;
        int tC = 0;
        int dR = martix.length - 1;
        int dC = martix[0].length - 1;
        while (tR < dR) {
            rotateEdge(martix, tR++, tC++, dR--, dC--);
        }
    }
    private void rotateEdge(int[][] m, int tR, int tC, int dR, int dC) {
        int times = dC - tC;
        int tmp = 0;
        for (int i = 0; i != times; i++) {
            tmp = m[tR][tC + i];
            m[tR][tC + i] = m[dR - i][tC];
            m[dR - i][tC] = m[dR][dC - i];
            m[dR][dC - i] = m[tR + i][dC];
            m[tR + i][dC] = tmp;
        }
    }

    public void printMatrixZigZag(int[][] martix) {
        int tR = 0;
        int tC = 0;
        int dR = 0;
        int dC = 0;
        int endR = martix.length - 1;
        int endC = martix[0].length - 1;
        boolean fromUp = false;
        while (tR != endR + 1) {
            printLevel(martix, tR, tC, dR, dC, fromUp);
            tR = (tC == endC ? tR + 1 : tR);
            tC = (tC == endC ? tC : tC + 1);
            dC = (dR == endR ? dC + 1 : dC);
            dR = (dR == endR ? dR : dR + 1);
            fromUp = !fromUp;
        }
        System.out.println();
    }
    private void printLevel(int[][] m, int tR, int tC, int dR, int dC, boolean flag) {
        if (flag) {
            while (tR != dR + 1) {
                System.out.print(m[tR++][tC--] + " ");
            }
        } else {
            while (dR != tR - 1) {
                System.out.print(m[dR--][dC++] + " ");
            }
        }
    }

    // topK 1.sort 2. heap 适合海量数据 3.quickSelect
    public ArrayList<Integer> minK(int[] arr, int k) {
        if (arr == null || k > arr.length) {
            return null;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>((o1,o2) -> o2 - o1);
        for (int num: arr
             ) {
            maxHeap.offer(num);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }

    public int getMinSortSubLength(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int min = arr[arr.length - 1];
        int noMinIndex = -1;
        for (int i = arr.length - 2; i >= 0; i--) {
            if (arr[i] > min) {
                noMinIndex = i;
            } else {
                min = Math.min(arr[i], min);
            }
        }
        if (noMinIndex == -1) {
            return 0;
        }
        int max = arr[0];
        int noMaxIndex = -1;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < max) {
                noMaxIndex = i;
            } else {
                max = Math.max(max, arr[i]);
            }
        }
        return noMaxIndex - noMinIndex + 1;
    }

    public int getMajor(int[] arr) {
        int cand = 0;
        int times = 0;
        for (int i = 0; i < arr.length; i++) {
            if (times == 0) {
                cand = arr[i];
                times++;
            } else if (arr[i] == cand) {
                times++;
            } else {
                times--;
            }
        }
        return cand;
    }

    public boolean searchInSortedMartix(int[][] martix, int target) {
        int row = 0;
        int col = martix[0].length - 1;
        while (row < martix.length && col >= 0) {
            if (martix[row][col] > target) {
                col--;
            } else if (martix[row][col] < target) {
                row++;
            } else {
                return true;
            }
        }
        return false;
    }



    public int gcd(int m, int n) {
        return n == 0 ? m : gcd(n, m % n);
    }

    public int zeroNumI(int n) {
        if (n < 0) {
            return 0;
        }
        int res = 0;
        int cur = 0;
        for (int i = 5; i <= n; i += 5) {
            cur = i;
            while (cur % 5 == 0) {
                res++;
                cur /= 5;
            }
        }
        return  res;
    }
    public int zeroNumII(int n) {
        if (n < 0) {
            return 0;
        }
        int res = 0;
        while (n != 0) {
                res += n / 5;
                n /= 5;
            }
        return  res;
    }

    public int rightOneI(int n) {
        if (n < 1) {
            return -1;
        }
        int res = 0;
        while (n != 0) {
                n >>>= 1;
                res += n;
            }
        return  res;
    }


    /**
     * 自然数数组排序,1-n  要求 o(n) o(1)
     * @param arr
     */
    public void sortI(int[] arr) {
        int tmp = 0;
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            tmp = arr[i];
            while (arr[i] != i + 1) {
                next = arr[tmp - 1];
                arr[tmp - 1] = tmp;
                tmp = next;
            }
        }
    }
    public void sortII(int[] arr) {
        int tmp = 0;
        for (int i = 0; i < arr.length; i++) {
            while (arr[i] != i + 1) {
                tmp = arr[arr[i] - 1];
                arr[arr[i] - 1] = arr[i];
                arr[i] = tmp;
            }
        }
    }

    public int minPathValue(int[][] m) {
        if (m == null || m.length == 0 || m[0].length == 0 || m[0][0] != 1 || m[m.length - 1][m[0].length - 1] != 1) {
            return 0;
        }
        int res = 0;
        int[][] dp = new int[m.length][m[0].length];
        dp[0][0] = 1;
        Queue<Integer> rQ = new LinkedList<>();
        Queue<Integer> cQ = new LinkedList<>();
        rQ.add(0);
        cQ.add(0);
        int r = 0;
        int c = 0;
        while (!rQ.isEmpty()) {
            r = rQ.poll();
            c = cQ.poll();
            if (r == m.length - 1 && c == m[0].length - 1) {
                return dp [r][c];
            }
            walkTo(dp[r][c], r - 1, c,m,dp,rQ,cQ);
            walkTo(dp[r][c], r, c - 1,m,dp,rQ,cQ);
            walkTo(dp[r][c], r + 1, c,m,dp,rQ,cQ);
            walkTo(dp[r][c], r, c + 1,m,dp,rQ,cQ);
        }
        return res;
    }
    private void walkTo(int pre, int toR, int toC,int[][] m,int[][] dp,Queue<Integer> rQ,Queue<Integer> cQ) {
        if (toR < 0 | toR == m.length || toC < 0 || toC == m[0].length || m[toR][toC] != 1 || dp[toR][toC] != 0) {
            return;
        }
        dp[toR][toC] = pre + 1;
        rQ.add(toR);
        cQ.add(toC);
    }

    /**
     * 最大子数组和
     * 全为负数即返回最大值,已经记录了.
     * @param arr
     * @return
     */
    public int maxSubArraySum(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < arr.length; i++) {
            cur += arr[i];
            max = Math.max(cur,max);
            cur = cur < 0 ? 0 : cur;
        }
        return max;
    }

    /**
     * 返回排序后相邻数最大差值 1.bf  2.桶排序 todo
     * @param nums
     * @return
     */
    public int maxGap(int[] nums) {
        int maxGap = 0;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            int cur = nums[i] - nums[i - 1];
            maxGap = Math.max(cur,maxGap);
        }
        return maxGap;
    }

    /**
     * 不含本位的累乘数组 1.除法 2.non / 两个数组
     * @param arr
     * @return
     */
    public int[] multipyArrayI(int[] arr) {
        if (arr == null || arr.length < 2) {
            return null;
        }
        int zeroCnt = 0;
        int all = 1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                all *= arr[i];
            } else {
                zeroCnt++;
            }
        }
        int[] res = new int[arr.length];
        if (zeroCnt == 0) {
            for (int i = 0; i < arr.length; i++) {
                res[i] = all / arr[i];
            }
        } else if (zeroCnt == 1) {
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 0) {
                    res[i] = all;
                }
            }
        }
        return res;
    }
    public int[] multipyArrayII(int[] a) {
        if (a == null || a.length < 1) {
            return null;
        }
        int[] res = new int[a.length];
        int[] lToR = new int[a.length];
        int[] rToL = new int[a.length];
        lToR[0] = a[0];
        rToL[a.length - 1] = a[a.length - 1];
        for (int i = 1; i < a.length; i++) {
            lToR[i] = lToR[i - 1] * a[i];
        }
        for (int i = a.length - 2; i >= 0; i--) {
            rToL[i] = rToL[i + 1] * a[i];
        }
        res[0] = rToL[1];
        res[a.length - 1] = lToR[a.length - 2];
        for (int i = 1; i <= a.length - 2; i++) {
            res[i] = lToR[i - 1] * rToL[i + 1];
        }
        return res;
    }

    /**
     * 找到局部最小 1.bf 2.二分
     * @param arr
     * @return
     */
    public int getLessIndexI(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        for (int i = 1; i <= arr.length - 2; i++) {
            if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) {
                return i;
            }
        }
        return -1;

    }
    public int getLessIndexII(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int lo = 1;
        int hi = arr.length - 2;
        int mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (arr[mid] > arr[mid - 1]) {
                hi = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }

        return lo;
    }

    /**
     *  子数组的最大累乘积 1.bf 2.dp
     * @param arr
     * @return
     */
    public double maxSubArrayMultipyI(double[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        double max = arr[0];
        for (int i = 0; i < arr.length - 1; i++) {
            double cur = arr[i];
            max = Math.max(max, cur);
            for (int j = i + 1; j < arr.length; j++) {
                cur *= arr[j];
                max = Math.max(max, cur);
            }
        }
        return max;
    }
    public double maxSubArrayMultipyII(double[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        double max = arr[0];
        double min = arr[0];
        double res = arr[0];
        double maxEnd;
        double minEnd;
        for (int i = 1; i < arr.length; i++) {
            maxEnd = max * arr[i];
            minEnd = min * arr[i];
            max = Math.max(Math.max(maxEnd,minEnd),arr[i]);
            min = Math.min(Math.min(maxEnd,minEnd),arr[i]);
            res = Math.max(max,min);
        }
        return res;
    }


    /**
     * 不重复打印排序数组中相加和为定值的所有二元组，三元组
     * @param arr
     * @param k
     */
    public void printUniquePair(int[] arr,int k) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int lo = 0;
        int hi = arr.length - 1;
        while (lo < hi) {
            if (arr[lo] + arr[hi] < k) {
                lo++;
            } else if (arr[lo] + arr[hi] > k) {
                hi--;
            } else {
                if (lo == 0 || arr[lo] != arr[lo - 1]) {
                    System.out.println(arr[lo] + " : " + arr[hi]);
                }
                lo++;
                hi--;
            }
        }
    }
    public void printUniqueTriad(int[] arr,int k) {
        if (arr == null || arr.length < 3) {
            return;
        }
        for (int i = 0; i < arr.length - 2; i++) {
            if (i == 0 || arr[i] != arr[i - 1]) {
                printRest(arr, i, i + 1, arr.length - 1, k - arr[i]);
            }
        }
    }
    private void printRest(int[] arr, int f, int l,int r,int k) {
        while (l < r) {
            if (arr[l] + arr[r] < k) {
                l++;
            } else if (arr[l] + arr[r] > k) {
                r--;
            } else {
                if (l == f + 1 || arr[l] != arr[l - 1]) {
                    System.out.println(arr[f] + " : " + arr[l] + " : " + arr[r]);
                }
                l++;
                r--;
            }
        }
    }

    @Test
    public void test() {
        System.out.println(rightOneI(5));
        /*int[][] m = {{1,2},{3,4}};
        spiralOrderPrint(m);*/
       /* int[] a = {1,1,1,9};
        printUniquePair(a,10);
        printUniqueTriad(a,11);*/
        /*double[] a = {2,3,1,4};
        System.out.println(maxSubArrayMultipyII(a));
        System.out.println(maxSubArrayMultipyI(a));*/
        // System.out.println(getLessIndexII(a));
        /*System.out.println(Arrays.equals(multipyArrayI(a),multipyArrayII(a)));
        int[] res = multipyArrayII(a);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }*/
        // System.out.println(maxSubArraySum(a));
       /* int[][] m = {{1,0,0},{1,0,0},{1,1,1}};
        System.out.println(minPathValue(m));*/
       /* int[] a = {1,2,5,3,4};
        sortI(a);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }*/
        /*ArrayList<Integer> res = minK(a, 2);
        for (int n: res
             ) {
            System.out.println(n);
        }*/
        //System.out.println(getMajor(a));
    }
}
